import random

def getRandintBits(size: int) -> int:
    """
    随机生成一个位数为size的整数, 且保证其最高位为1
    @size 必须为正数
    """
    return random.getrandbits(size) | (1 << (size - 1))

def MillerRabin(num):
    """
    Miller-Rabin素性检测 
    返回 num是否在10次Miller-Rabin检测后仍被认为很可能为素数
    """

    k, q = 0, num - 1

    # 计算 2^k * q = (n-1)
    while q % 2 == 0:
        q //= 2
        k += 1

    # 进行5次测试 (1/4)^5 准确率在99%以上
    for _ in  range(5):
        a = random.randrange(2,num-1)

        # 如果 a ^ q mod n = 1 | (n-1)  则n很可能为素数
        if pow(a,q,num) in (1,num-1):
            continue
        
        # 如果 a^((2^j)*q) mod n = n-1 则n很可能为素数
        for j in range(1,k):
            if pow(a,q*2**j,num) == (num-1):
                break
        # 但凡有一次没通过测试，num必为合数
        else:
            return False

    return True


def isPrime(num):
    """
    判断一个数是否是素数
    返回 num是否非常可能为素数
    """


    # 先使用1000以下的小素数进行检测 提高检测效率
    smallPrimes = [ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101,
                  103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199,
                  211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317,
                  331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443,
                  449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577,
                  587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701,
                  709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839,
                  853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983,
                  991, 997]

    if num in smallPrimes:
        return True

    for prime in smallPrimes:
        if num % prime == 0:
            return False

    return MillerRabin(num)

def generatePrime(size=1024):
    '''
    随机生成一个位数为size的素数
    '''
    while True:
        num = getRandintBits(size)
        if isPrime(num):
            return num
   

def xgcd(a: int, b: int) -> tuple:
    """
    拓展欧几里得算法
    返回 (x, y, g) : a * x + b * y = gcd(a, b) = g.
    """
    if a == 0:
        return 0, 1, b
    if b == 0:
        return 1, 0, a

    px, ppx = 0, 1
    py, ppy = 1, 0

    while b:
        q = a // b
        a, b = b, a % b
        x = ppx - q * px
        y = ppy - q * py
        ppx, px = px, x
        ppy, py = py, y

    return ppx, ppy, a


def invmod(a: int, n: int) -> int:
    """
    使用拓展欧几里得算法求模的逆元
    返回 1 / a (mod n).
    @a and @n 必须互质
    """
    x, y, g = xgcd(a, n)

    if g != 1:
        raise ValueError("no invmod for given @a and @n")
    else:
        return x % n


def textToHex(te: str) -> str:
    """
    将utf-8文本转为hex编码
    返回 he
    """
    he = '0x'
    for ch in te:
        he += hex(ord(ch))[2:]
    return he


def hexToText(he: str) -> str:
    """
    将hex编码转为utf-8文本
    返回 te
    """
    te = ''
    he = he[2:]
    while he:
        te += chr(eval("0x"+he[0:2]))  
        he = he[2:]
    return te


  



# for debug
# print(textToHex('mount'))
# print(getRandintBits(1))
# while True:
#     print(libnum.prime_test(generatePrime(2048)))
    # p = getRandintBits(1024)
#     bool = isPrime(p)
#     print(bool)
#     if not bool : 
#         print(p)
#         break
# print(generatePrime(1024))
# print(invmod(213,466))